package leetcode.sword;

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution59_1 {

    public static void main(String[] args) {
        Solution59_1 ss = new Solution59_1();
        int[] nums = {1,-1};
//        ArrayList<Integer> window = new ArrayList<>();
//        for (int num:nums) {
//            window.add(ss.findInsertPos(window,num),num);
//        }
////        window.remove(new Integer(343434));
//        System.out.println(window.toString());
        for (int max: ss.maxSlidingWindow(nums, 1)) {
            System.out.println(max);
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if(n<k||k<=0) return new int[0];
        int[] res = new int[n-k+1];
        int count = 0;
        LinkedList<Integer> maxQue = new LinkedList<Integer>();
        for(int i=0;i<n;i++){
            int num = nums[i];
            //保持队列单调减，从尾部出队
            while(!maxQue.isEmpty()&&nums[maxQue.peekLast()]<num){
                maxQue.removeLast();
            }
            maxQue.addLast(i);
            //检查是否队首过期
            if(maxQue.peekFirst()==i-k) maxQue.removeFirst();
            //获取窗口最大值
            if(i>=k-1) res[count++] = nums[maxQue.peekFirst()];
        }
        return res;
    }

    //单调队列
    public int[] maxSlidingWindow4(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        int[] res = new int[nums.length-k+1];
        LinkedList<Integer> decQueue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //入队并删除比当前小的元素
            while (!decQueue.isEmpty()&&decQueue.getLast()<nums[i]) decQueue.removeLast();
            decQueue.add(nums[i]);
            //判断是第一个窗口没有满还是开始滑动窗口了
            if (i > k-1) {
                //开始滑动,如果当前队首元素是上一个窗口的，删掉他
                if(decQueue.getFirst().equals(nums[i-k])) decQueue.removeFirst();
                //取队列首即当前窗口最大值
                res[i-k+1] = decQueue.getFirst();
            }else if(i==k-1){
                //第一次满,直接取队列首即可
                res[i-k+1] = decQueue.getFirst();
            }
        }
        return res;
    }

    //保持前一个窗口最大值，如果前一个窗口最大值被删掉，重新找最大值
    public int[] maxSlidingWindow3(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        int[] res = new int[nums.length-k+1];
        int curMaxInd = 0;
        for (int i = 0; i < nums.length; i++) {
            //判断是第一个窗口没有满还是开始滑动窗口了
            if (i > k-1) {
                if(nums[curMaxInd]<nums[i]){ //新的引入值比上个窗口最大值大
                    curMaxInd = i;
                }else {
                    //新的引入值比上个窗口最大值小,需判断上个窗口最大值是否被滑动出去了
                    if(curMaxInd==i-k){
                        //被滑出去要重新求当前窗口最大值位置
                        curMaxInd = maxIdx(nums,i-k+1,i);
                    }
                }
                res[i-k+1] = nums[curMaxInd];
            }else{
                if(nums[curMaxInd]<nums[i]) curMaxInd = i;
                if(i==k-1) res[i-k+1] = nums[curMaxInd];
            }
        }
        return res;
    }

    public int maxIdx(int[] nums, int start, int end){
        int tmpMaxIdx = start;
        for (int i=start+1;i<=end;i++){
            if(nums[tmpMaxIdx]<nums[i]) tmpMaxIdx = i;
        }
        return tmpMaxIdx;
    }



    //暴力版
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        int[] res = new int[nums.length-k+1];
        for (int i = 0; i < nums.length-k+1; i++) {
            res[i] = max(nums, i,i+k-1);
        }
        return res;
    }
    public int max(int[] nums, int start, int end){
        int tmpMax = nums[start];
        for (int i=start+1;i<=end;i++){
            if(tmpMax<nums[i]) tmpMax = nums[i];
        }
        return tmpMax;
    }

    //维持一个由小到大的有序数组
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        ArrayList<Integer> window = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //先插入
            window.add(findInsertPos(window,nums[i]),nums[i]);
            //判断是第一个窗口没有满还是开始滑动窗口了
            if (window.size() > k) {
                //已经开始滑动了，删除上一个窗口第一个元素
                window.remove(findInsertPos(window,nums[i-k]));
                //将当前窗口最大值加入res
                res[i-k+1] = window.get(k-1);
            }else if (window.size() == k) {
                //第一次滑动窗口满了
                res[i-k+1] = window.get(k-1);
            }
        }
        return res;
    }

    public int findInsertPos(ArrayList<Integer> arrayList, int value){
        //arrayList有序,可以二分查找
        int low = 0, high = arrayList.size()-1;
        while(low<=high){
            int mid = (low + high)>>1;
            if(arrayList.get(mid).equals(value)){
                return mid;
            }else if(arrayList.get(mid)>value){
                high = mid-1;
            }else {
                low = mid+1;
            }
        }
        return high+1;
    }

}
